#include<stdio.h>
#include<stdlib.h>
//
void insertsort(int*arr,int n)
{
	for(int i=0;i<n-1;i++)
	{
		int end = i;
		int tmp = arr[end+1];
		while (end+1)
		{
			if(tmp<arr[end])
			{ 
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}

			
		
		}
		arr[end + 1] = tmp;
	
	}



}

//ϣ
void shellsort(int *arr ,int n)
{
	    int gap=n;
		while (gap>1)
		{
			gap = gap / 3 + 1;
			for (int i = 0; i < n - gap; i++)
			{
				int end = i;
				int tmp = arr[end + gap];
				while (end >= 0)
				{
					if (tmp < arr[end])
					{
						arr[end + gap] = arr[end];
						end = end - gap;
					}
					else
					{
						break;
					}
				}
				arr[end + gap] = tmp;
			}
		}
}

//ѡ
void selectsort(int *arr,int n)
{
	int end = n - 1;
	int begen = 0;
	while (begen<end)
	{
		int min = begen;
		int max = begen;
		for (int i = begen+1; i <=end;i++)
		{
			if (arr[min] > arr[i])
			{
				min = i;
			}
			if (arr[max] < arr[i])
			{
				max = i;
			}
		}
		int tmp1 = arr[begen];
		arr[begen] = arr[min];
		arr[min] = tmp1;
		if (begen == max)
		{
			max = min;
		}
		int tmp2 = arr[end];
		arr[end] = arr[max];
		arr[max] = tmp2;
		end--;
		begen++;
	}




}

//ð
void BubbleSort(int* arr, int n)
{
	for (int i = n - 1; i>=0;i--)
	{
		for (int j = 0; j < i; j++)
		{   
			int a = 0;
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = tmp;
				a = 1;
			}
			if (a == 0)
			{
				break;
			}
		}
	}


}

//
void addjustdown(int *arr,int root,int n)
{
	int parent = root;
	int child = parent*2+1;
	while (child < n )
	{
		if (child<n-1&& arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[parent] < arr[child])
		{
			int tmp = arr[parent];
			arr[parent] = arr[child];
			arr[child] = tmp;
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}

}

void  headsort(int* arr, int n)
{
	//
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		addjustdown(arr, i, n);
	}
	int end = n - 1;
	while (end)
	{
		int tmp = arr[0];
		arr[0] = arr[end];
		arr[end] = tmp;
		addjustdown(arr, 0, end);
		end--;
	}
}

//
int partsort(int* arr, int begin, int end)
{
	    int key = end;
		while (begin < end)
		{
			while (begin<end && arr[begin] <= arr[key])
			{
				begin++;
			}
			while (begin < end && arr[end]>=arr[key])
			{
				end--;
			}

			int tmp = arr[end];
			arr[end] = arr[begin];
			arr[begin] = tmp;

	    }
		int tmp = arr[end];
		arr[end] = arr[key];
		arr[key] = tmp;


		return end;


}


void quicksort(int* arr, int left, int right)
{
	if (left >= right)
		return ;
	int div = partsort(arr, left, right);
	quicksort(arr, left, div - 1);
	quicksort(arr, div + 1,right);




}

//֮ǰָ
int partsort1(int* arr, int begin, int end)
{
	

	int prev = begin - 1;
	int cur = begin;
	int key = end;
	while (cur <= end)
	{
		if (arr[cur] < arr[key])
		{
			prev++;
			int tmp = arr[cur];
			arr[cur] = arr[prev];
			arr[prev] = tmp;
		}
		cur++;
	}

	prev++;
	int tmp = arr[prev];
	arr[prev] = arr[end];
	arr[end] = tmp;
	
	return prev;



}
//鲢


void gbpartsort(int * tmp,int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	gbpartsort(tmp,arr, begin, mid);
	gbpartsort(tmp,arr, mid+1, end);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int key = begin1;
	while (begin1<=end1 && begin2<=end2)
	{
		if (arr[begin1]<arr[begin2])
		{
			tmp[key++] = arr[begin1++];
		}
		else
		{
			tmp[key++] = arr[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[key++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[key++] = arr[begin2++];
	}
	for (int i = begin; i <= end; i++)
	{
		arr[i] = tmp[i];
	}
}




void gbsort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);

	gbpartsort(tmp, arr, 0, n - 1);

	free(tmp);

}

//鲢֮ǵݹ
	
void quicksort1(int * arr,int begin ,int end)
{
	if (begin >= end)
		return ;
	int div=partsort1(arr, begin, end);
	
	quicksort1(arr,begin,div-1);
	quicksort1(arr, div+1, end);

}



void gbnpartsort(int* arr, int* tmp, int begin1, int end1, int begin2, int end2)
{
	int key = begin1;
	int begin = begin1, end = end2;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[key++] = arr[begin1++];
		}
		else
		{
			tmp[key++] = arr[begin2++];


		}
		//printf("1");
	}
    while (begin1 <= end1)
	{
		tmp[key++] = arr[begin1++];
		//printf("2");

	}
	while (begin2 <= end2)
	{
		tmp[key++] = arr[begin2++];
		//printf("3");

	}
	
	for (int i = begin; i <= end; i++)
	{
		arr[i] = tmp[i];
	}


}

void gbnsort(int *arr,int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			gbnpartsort(arr, tmp, begin1, end1, begin2, end2);

			//printf("4");

		}
		gap *= 2;
	}
	free(tmp);
	
}

//ļ
//非比较排序
void countsort(int* arr, int n)
{
	int range=0, min=0, max=0;
	for (int i = 0; i < n; i++)
	{
		if (arr[min] > arr[i])
		{
			min = i;
		}

		if (arr[max] < arr[i])
		{
			max = i;
		}
	}
	range = arr[max] - arr[min]+1;
	int j = arr[min];
	int* tmp = (int*)malloc(sizeof(int) * range);
	memset(tmp, 0, sizeof(int) * range);
	int key = 0;
	for (int i = 0; i < n; i++)
	{
		tmp[arr[i]-j]++;
	}
	for (int i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			arr[key++] = i + j;
		}
	}




	free(tmp);



}

int main()
{
	int arr[9] = { 2,6,5,9,5,9,91,5,8};
	gbnsort(arr,9);
	for (int i = 0; i < 9; i++)
	{
		printf("%d", arr[i]);
	}


	return 0;
}
